package com.zyk.leetcode;

import java.util.LinkedList;

/**
 * @author zhangsan
 * @date 2021/4/21 15:40
 */
public class C641 {

    static class MyCircularDeque {

        Node head, tail;

        int capacity;
        int size;

        /** Initialize your data structure here. Set the size of the deque to be k. */
        public MyCircularDeque(int k) {
            capacity= k;
        }

        /** Adds an item at the front of Deque. Return true if the operation is successful. */
        public boolean insertFront(int value) {
            if(isFull()) return false;
            Node cur;
            if(size == 0) {
                cur = new Node(value);
                head = cur;
                tail = cur;
            }else {
                cur = new Node(null, head, value);
                head.pre = cur;
                head = cur;
            }
            size++;
            return true;
        }

        /** Adds an item at the rear of Deque. Return true if the operation is successful. */
        public boolean insertLast(int value) {
            if(isFull()) return false;
            Node cur;
            if(size == 0) {
                cur = new Node(value);
                head = cur;
                tail = cur;
            }else {
                cur = new Node(tail, null, value);
                tail.next = cur;
                tail = cur;
            }
            size++;
            return true;
        }

        /** Deletes an item from the front of Deque. Return true if the operation is successful. */
        public boolean deleteFront() {
            if(isEmpty()) return false;
            if(size == 1) {
                head = null;
                tail = null;
            }else {
                Node next = head.next;
                next.pre = null;
                head = next;
            }
            size--;
            return true;
        }

        /** Deletes an item from the rear of Deque. Return true if the operation is successful. */
        public boolean deleteLast() {
            if(isEmpty()) return false;
            if(size == 1) {
                head = null;
                tail = null;
            }else {
                Node pre = tail.pre;
                pre.next = null;
                tail = pre;
            }
            size--;
            return true;
        }

        /** Get the front item from the deque. */
        public int getFront() {
            return head == null ? -1 : head.v;
        }

        /** Get the last item from the deque. */
        public int getRear() {
            return tail == null ? -1 : tail.v;
        }

        /** Checks whether the circular deque is empty or not. */
        public boolean isEmpty() {
            return size == 0;
        }

        /** Checks whether the circular deque is full or not. */
        public boolean isFull() {
            return size == capacity;
        }


        private static class Node {
            Node pre, next;
            int v;

            public Node(int v) {
                this.v = v;
            }

            public Node(Node pre, Node next, int v) {
                this.pre = pre;
                this.next = next;
                this.v = v;
            }
        }
    }

    static class Right {

        LinkedList<Integer> deque;
        int k;
        int size;

        /** Initialize your data structure here. Set the size of the deque to be k. */
        public Right(int k) {
            this.k = k;
            deque = new LinkedList<>();
        }

        /** Adds an item at the front of Deque. Return true if the operation is successful. */
        public boolean insertFront(int value) {
            if(size >= k) return false;
            deque.addFirst(value);
            size++;
            return true;
        }

        /** Adds an item at the rear of Deque. Return true if the operation is successful. */
        public boolean insertLast(int value) {
            if(size >= k) return false;
            deque.addLast(value);
            size++;
            return true;
        }

        /** Deletes an item from the front of Deque. Return true if the operation is successful. */
        public boolean deleteFront() {
            if(size == 0) return false;
            size--;
            return deque.pollFirst() != null;
        }

        /** Deletes an item from the rear of Deque. Return true if the operation is successful. */
        public boolean deleteLast() {
            if(size == 0) return false;
            size--;
            return deque.pollLast() != null;
        }

        /** Get the front item from the deque. */
        public int getFront() {
            if(size == 0) return -1;
            return deque.peekFirst();
        }

        /** Get the last item from the deque. */
        public int getRear() {
            if(size == 0) return -1;
            return deque.peekLast();
        }

        /** Checks whether the circular deque is empty or not. */
        public boolean isEmpty() {
            return size == 0;
        }

        /** Checks whether the circular deque is full or not. */
        public boolean isFull() {
            return size == k;
        }
    }


    // for test
    public static void main(String[] args) {
        Right circularDeque = new Right(3);
        System.out.println(circularDeque.insertLast(1));
        System.out.println(circularDeque.insertLast(2));
        System.out.println(circularDeque.insertFront(3));
        System.out.println(circularDeque.insertFront(4));
        System.out.println(circularDeque.getRear());
        System.out.println(circularDeque.isFull());
        System.out.println(circularDeque.deleteLast());
        System.out.println(circularDeque.insertFront(4));
        System.out.println(circularDeque.getFront());
        System.out.println("=========================");
        MyCircularDeque circularDeque2 = new MyCircularDeque(3);
        System.out.println(circularDeque2.insertLast(1));
        System.out.println(circularDeque2.insertLast(2));
        System.out.println(circularDeque2.insertFront(3));
        System.out.println(circularDeque2.insertFront(4));
        System.out.println(circularDeque2.getRear());
        System.out.println(circularDeque2.isFull());
        System.out.println(circularDeque2.deleteLast());
        System.out.println(circularDeque2.insertFront(4));
        System.out.println(circularDeque2.getFront());

    }

}
